Read the original article here.

---

Asynchronous Circuits: An Innovation Ahead of Its Time

Introduction: The Clockless Revolution That Almost Was

In the relentless pursuit of faster, more efficient computing, engineers have explored numerous innovative approaches to digital circuit design. Among these, asynchronous circuits, also known as clockless or self-timed circuits, stand out as a particularly compelling, yet often overlooked, innovation. Imagine a world where computer chips didn't rely on a global clock to orchestrate their operations, a world where components communicated and processed data based on demand, potentially leading to significant gains in speed and energy efficiency. This is the promise of asynchronous circuits.

While synchronous circuits, governed by a central clock signal, dominate modern digital devices, asynchronous circuits offer a fundamentally different paradigm. They represent a fascinating "road not taken" in the history of computing, a path that, despite demonstrating significant potential, has remained largely in the realm of research and niche applications. Exploring asynchronous circuits provides valuable insights into alternative design philosophies and highlights the trade-offs inherent in different approaches to digital logic. In the context of "lost computer innovations ahead of their time," asynchronous circuits serve as a prime example of a technology with compelling advantages that faced significant hurdles in widespread adoption, especially in the face of the established dominance of synchronous design methodologies.

Understanding Synchronous vs. Asynchronous Circuits: The Fundamental Difference

To grasp the significance of asynchronous circuits, it's crucial to understand the prevailing paradigm: synchronous circuits.

Synchronous Circuits: The Rhythm of the Clock

Synchronous Circuit: A type of sequential digital logic circuit where the timing of all operations is controlled by a global clock signal. This signal is a repetitive pulse that acts as a central metronome, ensuring that all components of the circuit change their state in a coordinated manner.

In synchronous circuits, a central clock signal, generated by an electronic oscillator, dictates the pace of operations. This clock signal is distributed throughout the entire integrated circuit (IC), reaching every component. Think of it like a conductor in an orchestra, ensuring every instrument plays in time. Key components like flip-flops, which are fundamental memory elements, only change their state when triggered by a specific edge (rising or falling) of the clock pulse.

This synchronized operation has a critical implication: changes in signal values across the entire circuit begin at roughly the same time and at regular intervals dictated by the clock. The output of all memory elements at any given clock pulse defines the state of the synchronous circuit. The state only updates on the clock pulse, creating discrete time steps for computation.

However, this synchronization comes with its own set of challenges.

Challenges of Synchronous Circuits: Clock Skew and Critical Path

Modern synchronous IC design faces significant challenges in timing, demanding extensive engineering effort and sophisticated design automation tools.

• Clock Skew:

  Clock Skew: The phenomenon where the clock signal arrives at different parts of a synchronous circuit at slightly different times. In large, complex ICs, distributing the clock signal perfectly uniformly across the entire chip becomes increasingly difficult.

  Imagine the conductor's baton reaching different sections of the orchestra at slightly different moments – this is clock skew. In high-speed, large-scale ICs, the physical distance and varying impedances of the clock distribution network cause delays. This means the clock edge, intended to trigger simultaneous operations, arrives at different components at slightly different times. Clock skew can lead to timing errors and malfunctions if not carefully managed. Designers must employ complex techniques to minimize and compensate for clock skew, adding to design complexity and overhead.

• Critical Path and Clock Speed Limits:

  Critical Path: The longest sequence of logic gates in a synchronous circuit that a signal must traverse between clock pulses. The delay along the critical path dictates the minimum time between clock pulses, and thus the maximum clock frequency of the circuit.

  The speed of a synchronous circuit is fundamentally limited by its critical path. Signals take time to propagate through logic gates – this delay is known as propagation delay. The critical path represents the slowest path for a signal to travel within one clock cycle. The clock period must be long enough to accommodate the propagation delay of the critical path. Consequently, even if most parts of the circuit could operate much faster, the entire system is constrained by the slowest component. This means parts of the circuit are often idle, waiting for the clock cycle to complete, even if they could have finished their operations much earlier.

• Power Dissipation:

  A widely distributed clock network consumes significant power. The clock signal constantly toggles, even when the circuit is idle or waiting for inputs. This continuous clock activity contributes to unnecessary power dissipation.

• Testing and Debugging Complexity:

  Synchronous circuits, while seemingly simpler conceptually, become increasingly complex to test and debug as their size and complexity grow. Ensuring correct timing across all parts of a large synchronous design and diagnosing timing-related issues can be a major undertaking, often consuming a significant portion of the development time.

Asynchronous Circuits: Operating on Demand

Asynchronous Circuit: A type of sequential digital logic circuit that does not rely on a global clock signal for synchronization. Instead, components communicate and synchronize using handshaking circuits. Operations are triggered by the completion of preceding operations, making them data-driven rather than clock-driven.

Asynchronous circuits break free from the constraints of a global clock. Instead of being paced by a central clock, components in an asynchronous circuit operate and communicate based on handshaking.

• Handshaking: Communication and Synchronization:

  Handshaking Circuit: A circuit used in asynchronous designs to control the flow of data and synchronize operations between components. It involves communication signals, typically "request" and "acknowledge," exchanged between modules to indicate data availability and completion of operations.

  Handshaking is a communication protocol between different parts of the asynchronous circuit. Imagine two people passing a package. One person (the sender) signals they have the package ready (a "request"). The other person (the receiver), upon receiving the package, signals back that they have received it and are ready for the next one (an "acknowledge"). This back-and-forth signaling mechanism replaces the global clock in coordinating operations.

  When a component in an asynchronous circuit completes its task, it signals its completion to the next component in the processing chain. This signal then triggers the next component to begin its operation. This data-driven approach allows each part of the circuit to operate as quickly as it can, without waiting for a global clock cycle.

Potential Advantages and Challenges of Asynchronous Circuits

• Potential Speed Advantage: Asynchronous circuits are theoretically capable of operating faster than synchronous circuits. Their speed is limited only by the propagation delays of the logic gates and interconnections, not by a fixed clock cycle determined by the worst-case path. They can operate at their average-case performance rather than being bound by the worst-case scenario dictated by the critical path in synchronous designs.

• Lower Power Consumption: Asynchronous circuits only consume power when they are actively processing data. Since there's no global clock continuously toggling, power is saved during idle periods. This "on-demand" operation can lead to significantly lower power consumption, especially in applications with variable workloads or periods of inactivity.

• Reduced Electromagnetic Interference (EMI): Synchronous circuits, with their periodic clock signal, generate EMI concentrated around the clock frequency and its harmonics. Asynchronous circuits, lacking a global clock, produce EMI that is more spread across the frequency spectrum, potentially reducing peak EMI levels.

• Modularity and Robustness: Asynchronous designs can be more modular, making it easier to reuse and integrate different functional blocks. They can also be more robust to variations in manufacturing processes, temperature, and voltage, as they are not critically dependent on precise timing constraints dictated by a global clock.

• Design Complexity and Race Conditions: Designing asynchronous circuits is generally more complex than designing synchronous circuits. One significant challenge is managing race conditions.

  Race Condition: A situation in asynchronous circuits where the final state of the circuit depends on the relative arrival times of input signals at logic gates. If signals arrive at almost the same time, slight variations in gate delays can lead to unpredictable and incorrect circuit behavior.

  Race conditions arise because the timing of events in asynchronous circuits is not strictly controlled by a clock. If two inputs to a gate change state nearly simultaneously, the output might transition to an incorrect state before settling to the intended state. While synchronous circuits are less prone to race conditions (primarily due to asynchronous inputs from outside the synchronous system), asynchronous circuits require careful design techniques to avoid or mitigate race conditions.

• Testing and Debugging Challenges: Testing and debugging asynchronous circuits can be more challenging than their synchronous counterparts. The lack of a global clock makes it harder to establish a consistent time reference for observing and analyzing circuit behavior. Specialized techniques and tools are needed to effectively test and debug asynchronous designs.

Theoretical Foundation: Building Logic Without a Clock

The theoretical underpinnings of asynchronous circuits were established in the mid-1950s by David E. Muller. His work laid the foundation for a new way of thinking about digital logic, moving beyond the constraints of synchronous timing. This early theory was later elaborated upon in Raymond Miller's influential book "Switching Theory."

Asynchronous Logic: Beyond Boolean Algebra

Asynchronous Logic: The logical framework required for designing asynchronous digital systems. It extends beyond traditional Boolean logic to account for the absence of a global clock and the potential for elements to be in indeterminate states during transitions.

Traditional Boolean logic, with its focus on discrete true/false states, is insufficient for fully describing the behavior of asynchronous circuits where elements are not guaranteed to be in a stable state at any given time. Asynchronous logic necessitates extensions to handle the continuous nature of signal transitions and the potential for intermediate or undefined states.

• Vassuming the Time Dimension: Venjunction and Sequention

  Vadim O. Vasyukevich pioneered an approach based on new logical operations, venjunction and sequention, introduced in 1984.

  • Vjunction: Represented as "x∠y", venjunction signifies "switching x on the background y" or "if x when y then". This operation considers the context of a signal's change relative to another signal.
  • Sequention: Uses priority signs "x_i≻x_j" and "x_i≺x_j" to define the order of events, explicitly capturing the temporal relationships between signals.

  These operations move beyond simple Boolean values to incorporate the history and timing of signal changes, making them more suitable for describing asynchronous behavior.

• Four-Valued Logic and Null Convention Logic (NCL)

  Karl M. Fant, in his 2005 work "Logically determined design," developed a different theoretical framework using four-valued logic. This logic introduces two additional states beyond true and false: null and intermediate.

  • Null: Represents an absence of data or a reset state.
  • Intermediate: Represents a transitional state between true and false (or vice versa).

  This four-valued logic is crucial for Null Convention Logic (NCL), a quasi-delay-insensitive asynchronous design style.

  Null Convention Logic (NCL): An asynchronous logic family based on four-valued logic, designed to be quasi-delay-insensitive. It uses "null" and "data" states to represent the absence and presence of valid data, respectively, ensuring robust operation even with variations in gate and wire delays.

  NCL is significant because it aims for quasi-delay-insensitivity.

  Quasi-Delay-Insensitive (QDI) Design: An approach to asynchronous circuit design that aims to minimize or eliminate assumptions about gate and wire delays. QDI circuits are designed to function correctly even with significant variations in delays, enhancing robustness and making them "correct by design."

  Scott C. Smith and Jia Di further refined NCL by developing Multi-threshold Null Convention Logic (MTNCL) or Sleep Convention Logic (SCL). This variation incorporates multi-threshold CMOS technology to achieve ultra-low power operation, making NCL more practical for energy-sensitive applications.

Petri Nets: Modeling Asynchronous Concurrency

Petri Nets: A mathematical modeling language for describing and analyzing systems with concurrent and asynchronous events. They are particularly well-suited for modeling asynchronous circuits due to their ability to represent concurrency, synchronization, and resource sharing.

Signal Transition Graphs (STGs): A type of interpreted Petri net specifically tailored for modeling asynchronous circuits. STGs represent signal transitions as events and the causal relationships between these transitions, providing a graphical and formal method for analyzing and synthesizing asynchronous control circuits.

Petri nets provide a powerful graphical and mathematical framework for reasoning about asynchronous circuits. They excel at modeling concurrent processes, synchronization, and resource sharing, which are fundamental aspects of asynchronous behavior.

Signal Transition Graphs (STGs), developed independently in 1985 by Leonid Rosenblum, Alex Yakovlev, and Tam-Anh Chu, are a specialized type of Petri net designed specifically for asynchronous circuit modeling. STGs represent signal transitions (changes from 0 to 1 or 1 to 0) as events in the Petri net and depict the dependencies and causal relationships between these transitions.

STGs have become a cornerstone of asynchronous circuit design theory and practice. They have led to the development of software tools like Petrify and Workcraft, which are used for analysis and synthesis of asynchronous control circuits.

Beyond Petri nets, other models of concurrency, such as the Actor model and process calculi, have also been explored for modeling asynchronous systems, offering alternative perspectives and tools for asynchronous circuit design.

Benefits of Asynchronous Circuits: Advantages Ahead of Their Time

Asynchronous circuits offer a compelling set of advantages, many of which were particularly relevant even in earlier eras of computing and are becoming increasingly critical in modern chip design. These benefits highlight why asynchronous circuits were considered an innovation ahead of their time.

• Robust and Cheap Handling of Metastability:

  Asynchronous circuits naturally handle metastability in arbiters more robustly and cost-effectively than synchronous designs.

  Metastability: An unstable state in a digital circuit, particularly in flip-flops or latches, where the output remains in an indeterminate state for an unpredictable duration before settling to a valid logic level (0 or 1). Metastability can occur when asynchronous inputs violate setup and hold time requirements.

  When dealing with asynchronous inputs or arbitration (deciding which of multiple requests gets access to a shared resource), circuits can enter a metastable state. In synchronous circuits, metastability requires special handling, often involving complex synchronization circuitry and potential performance penalties. Asynchronous circuits, by their nature, are more tolerant to metastability, as the handshaking mechanism can naturally accommodate the indeterminate settling time without disrupting overall operation.

• Average-Case Performance: Breaking Free from Worst-Case Constraints:

  Unlike synchronous circuits whose speed is limited by the worst-case delay of the critical path, asynchronous circuits can achieve average-case performance. They are not constrained by the slowest possible operation and can adapt to variations in processing times.

  • Speculative Completion: Techniques like speculative completion leverage the average-case performance advantage. For example, asynchronous parallel prefix adders can be designed to be faster than their synchronous counterparts by predicting and speculatively completing operations before all inputs are fully stable.
  • High-Performance Arithmetic: Asynchronous designs have demonstrated superior performance in arithmetic units. For instance, high-performance double-precision floating-point adders have been built that outperform leading synchronous designs by capitalizing on the ability to complete operations faster when inputs allow.

• Early Completion: Speeding Up Predictable Operations:

  Asynchronous circuits can implement early completion, generating outputs as soon as the result of input processing is available, even if it is before the "worst-case" completion time.

  This is particularly advantageous when processing data where results can be predicted or become irrelevant quickly. For example, in certain signal processing applications, if the initial part of the input data is sufficient to determine the output, an asynchronous circuit can produce the result without waiting for the entire input to be processed, leading to faster response times.

• Inherent Elasticity: Graceful Handling of Variable Data Rates:

  Asynchronous circuits exhibit inherent elasticity, meaning they can handle variable rates of data input and output in pipelines.

  Pipeline: A series of processing stages connected in sequence, where the output of one stage becomes the input of the next. Pipelining is used to improve throughput by allowing multiple operations to be in progress simultaneously.

  In asynchronous pipelines, functional blocks (stages) are not rigidly synchronized by a clock. Variable numbers of data items can enter the pipeline at any time, and each stage processes data as quickly as it can. This elasticity allows asynchronous pipelines to gracefully adapt to fluctuating input and output rates without requiring complex buffering or flow control mechanisms. While congestion can still occur, the unclocked nature of pipeline stages allows for more flexible and efficient handling of variable data flow.

• Freedom from Clock Skew and Clock Distribution Challenges:

  Asynchronous circuits completely eliminate the clock skew problem and the complexities of distributing a high-fan-out, timing-sensitive clock signal across large ICs.

  This simplification reduces design effort, power consumption associated with clock distribution networks, and potential timing-related errors caused by clock skew.

• Adaptability to Changing Conditions: Dynamic Speed Adjustment:

  The speed of asynchronous circuits adapts dynamically to changing temperature and voltage conditions. They are not locked to a fixed clock speed determined by worst-case assumptions.

  As temperature decreases or voltage increases, transistors operate faster. Asynchronous circuits automatically take advantage of these improved operating conditions to increase their processing speed, without requiring any external adjustments. Conversely, if conditions worsen (e.g., higher temperature), they will slow down gracefully, maintaining correct operation but at a reduced speed. This adaptability is a significant advantage over synchronous circuits, which must be designed for worst-case scenarios and cannot dynamically optimize performance based on operating conditions.

• Lower, On-Demand Power Consumption: Energy Efficiency:

  Asynchronous circuits offer lower and on-demand power consumption. They consume power only when active and can achieve near-zero standby power consumption when idle.

  • Reduced Clock Power: The absence of a global clock eliminates the power consumed by the clock distribution network and clock drivers, which can be a significant portion of the total power budget in synchronous circuits.
  • Activity-Based Power: Power consumption is directly tied to activity. Only the parts of the circuit that are actively processing data consume power at any given time. In contrast, synchronous circuits often have significant power consumption even when idle due to continuous clock activity.
  • Epson's Example: Epson reported a 70% reduction in power consumption in an asynchronous design compared to a synchronous counterpart in 2005, highlighting the potential for significant energy savings.

• Robustness to Process Variations and Environmental Factors:

  Asynchronous circuits exhibit greater robustness to transistor-to-transistor variability in manufacturing, variations in voltage supply, temperature, and fabrication process parameters.

  The delay-insensitive or quasi-delay-insensitive nature of many asynchronous design styles makes them less sensitive to variations that can significantly impact the timing and reliability of synchronous circuits, especially as transistor sizes shrink and manufacturing tolerances become tighter.

• Less Severe Electromagnetic Interference (EMI):

  Asynchronous circuits generate less severe EMI compared to synchronous circuits.

  Synchronous circuits concentrate EMI around the clock frequency and its harmonics, potentially causing interference with other electronic systems. Asynchronous circuits, lacking a periodic clock, distribute EMI more evenly across the frequency spectrum, reducing peak EMI levels and making them potentially more EMC (electromagnetic compatibility) friendly.

• Design Modularity, Noise Immunity, and Electromagnetic Compatibility (EMC):

  Asynchronous circuits are often more modular, promoting design reuse and easier integration of different functional blocks. They also exhibit improved noise immunity and electromagnetic compatibility due to their reduced EMI and inherent tolerance to timing variations. They are less susceptible to noise glitches and voltage fluctuations compared to synchronous circuits that rely on precise clock timing.

Disadvantages of Asynchronous Circuits: Challenges to Mainstream Adoption

Despite their compelling advantages, asynchronous circuits have faced significant challenges that have hindered their widespread adoption and contributed to their status as a "lost" innovation in mainstream computing.

• Area Overhead due to Handshaking Logic:

  Asynchronous circuits typically incur an area overhead due to the additional logic required to implement handshaking protocols and completion detection mechanisms.

  The handshaking circuits, which replace the global clock for synchronization, add extra gates and interconnections to the design. In some cases, asynchronous designs can require up to twice the area of equivalent synchronous designs. This area overhead can translate to increased chip cost and potentially higher power consumption if leakage currents become significant, especially in older deep submicrometer processes.

• Design Complexity and Lack of Trained Designers:

  Designing asynchronous circuits is generally considered more complex than synchronous design. Historically, there has been a lack of trained engineers and designers experienced in asynchronous methodologies.

  The absence of a global clock and the need to manage handshaking protocols and potential race conditions require a different design mindset and specialized techniques. The learning curve for asynchronous design can be steeper, and the pool of experienced asynchronous designers has been smaller compared to the vast community familiar with synchronous design.

• Testing and Debugging Difficulties:

  Testing and debugging asynchronous circuits are often perceived as more challenging than for synchronous circuits.

  The lack of a global clock makes it harder to establish a consistent time reference for observation and analysis. Traditional synchronous testing methodologies and tools are not directly applicable to asynchronous designs. While some argue that asynchronous circuits can be designed for testability, the perceived complexity of testing has been a barrier to wider adoption.

• Clock Gating as a Synchronous Alternative:

  Clock gating in synchronous designs provides a simpler approximation of the power-saving benefits of asynchronous circuits.

  Clock Gating: A power-saving technique used in synchronous circuits where the clock signal to inactive parts of the circuit is selectively disabled, reducing dynamic power consumption.

  Clock gating allows synchronous circuits to reduce power consumption by turning off the clock to idle circuit blocks. While not as fine-grained or inherently power-efficient as asynchronous operation, clock gating offers a relatively straightforward way to achieve some power savings in synchronous designs. In some applications, the simplicity of clock gating might outweigh the perceived complexity and overhead of a fully asynchronous design.

• Performance Limitations in Input-Complete Architectures:

  The performance (speed) of asynchronous circuits can be reduced in architectures that require input-completeness, where all inputs must be stable before processing can begin.

  In certain data path designs, ensuring that all input data is valid and stable before initiating an operation can introduce delays in asynchronous circuits, potentially diminishing their speed advantage compared to synchronous designs in such scenarios.

• Lack of Dedicated Commercial EDA Tools:

  Historically, there has been a lack of dedicated, asynchronous design-focused commercial Electronic Design Automation (EDA) tools.

  The EDA tool ecosystem has been predominantly geared towards synchronous design methodologies. The limited availability of mature, user-friendly, and commercially supported EDA tools specifically tailored for asynchronous design has been a significant obstacle. While the situation has been slowly improving with some specialized tools emerging, the tool support for asynchronous design remains less comprehensive compared to the mature toolchains available for synchronous design.

Communication in Asynchronous Circuits: Handshaking Protocols and Data Encoding

Effective communication between components is crucial in asynchronous circuits, as they lack a global clock to synchronize data transfer. This communication relies on specific protocols and data encoding schemes.

Protocols: Two-Phase and Four-Phase Handshaking

Asynchronous communication protocols are broadly categorized into two main families based on how communication events are encoded:

• Two-Phase Handshake (Non-Return-to-Zero - NRZ, Transition Signaling):

  Two-Phase Handshake: An asynchronous communication protocol where any transition (0 to 1 or 1 to 0) on a wire signals a communication event. It is also known as Non-Return-to-Zero (NRZ) encoding or transition signaling because the signal does not necessarily return to a zero state between communications.

  In two-phase handshaking, any transition on a signal wire, whether from 0 to 1 or 1 to 0, is considered a communication event. Both types of transitions are meaningful and represent data transfer. This protocol is conceptually simple but can lead to more complex circuit implementations as the circuit needs to remember the current state of the signal line internally.

• Four-Phase Handshake (Return-to-Zero - RZ):

  Four-Phase Handshake: An asynchronous communication protocol where a communication event is represented by a transition sequence: typically a transition from 0 to 1 followed by a return transition from 1 to 0. It is also known as Return-to-Zero (RZ) encoding because the signal returns to a zero state after each communication.

  Four-phase handshaking uses a sequence of transitions to represent a single communication. A typical four-phase cycle involves a transition from 0 to 1, signifying a request or data availability, followed by a transition back to 0, indicating completion or acknowledgement. Despite requiring more transitions per communication, four-phase protocols often lead to simpler and faster circuit implementations because the signal lines return to a defined reset state (typically 0) after each communication cycle. This return-to-zero behavior simplifies state management within the circuits.

While these are the two primary protocol families, a wide variety of asynchronous protocols exist. Some protocols only encode requests and acknowledgements, while others also embed data within the handshake signals. Multi-wire data encoding, discussed below, is a common example of protocols that integrate data into the communication signals. Less common protocols include single-wire request/acknowledgement schemes, multi-voltage signaling, pulse-based signaling, and timing-balanced approaches that aim to eliminate the need for latches by carefully controlling signal timings.

Data Encoding: Bundled-Data and Multi-Rail Approaches

Data encoding in asynchronous circuits determines how data is represented and transmitted along with communication signals. Two widely used approaches are:

• Bundled-Data Encoding:

  Bundled-Data Encoding: An asynchronous data encoding scheme where data bits are transmitted on separate wires, similar to synchronous circuits. A separate request signal is bundled with the data to indicate data validity, and an acknowledge signal confirms data reception. It relies on timing assumptions to ensure data arrives before the completion signal.

  Bundled-data encoding closely resembles synchronous data transmission. Each bit of data is carried on a dedicated wire. In addition, separate request and acknowledge signals are used for handshaking, typically employing either a two-phase or four-phase protocol. The "bundled" aspect refers to the data being sent alongside a request signal.

  Bundled-data circuits often operate under a bounded delay model. This means they assume that the delay of the data path is always less than a certain known bound. The completion signal (acknowledgement) is delayed sufficiently to ensure that the data has had enough time to propagate and be valid at the receiver before the acknowledgement is asserted. These circuits are often referred to as micropipelines, a term initially coined for two-phase bundled-data designs, but now broadly used for bundled-data circuits regardless of the handshake protocol.

• Multi-Rail Encoding:

  Multi-Rail Encoding: An asynchronous data encoding scheme where data is encoded using multiple wires, without a one-to-one correspondence between bits and wires. Data availability is signaled by transitions on the data wires themselves, eliminating the need for a separate request signal. This approach is inherently delay-insensitive.

  Multi-rail encoding uses multiple wires to represent data, but unlike bundled-data, there isn't a direct mapping of one wire per bit. Instead, the presence of a transition on one or more of the data wires itself indicates the availability of data. This eliminates the need for a separate request signal, as data validity is inherently signaled by the data transitions. Multi-rail encoding offers delay-insensitivity as the data communication is self-timed and not reliant on timing assumptions.

  Common multi-rail encodings include:

  • One-Hot Encoding (1-of-n): Represents a base-n number using n wires. A communication event occurs on exactly one of the n wires to indicate the value. For example, in 1-of-4 encoding, four wires represent values 0, 1, 2, and 3, with a transition on wire 0 indicating value 0, wire 1 indicating value 1, and so on.
  • Dual-Rail Encoding (1-of-2): Uses pairs of wires to represent each bit of data. One wire in the pair represents a bit value of 0, and the other represents a bit value of 1. For example, a dual-rail encoded 2-bit number would use four wires (two pairs). To transmit a bit value, a transition occurs on either the "0-rail" or the "1-rail" of the corresponding pair.

  Dual-rail encoding with a four-phase protocol is particularly prevalent and is often called three-state encoding. It has two valid states (10 and 01, after a transition) representing 0 and 1, and a reset state (00). Four-state encoding or level-encoded dual-rail is another variation that uses a data bit and a parity bit to achieve a two-phase protocol and a simpler implementation than one-hot, two-phase dual-rail.

Asynchronous CPUs: A Visionary Concept of Clockless Processing

Asynchronous CPU (Clockless Processor): A central processing unit (CPU) designed using asynchronous circuit principles, eliminating the need for a central clock signal to coordinate operations. Stages of the CPU pipeline are coordinated using handshaking logic, enabling data-driven operation and potential performance and power advantages.

Asynchronous CPUs represent a radical departure from conventional synchronous processor design. Instead of relying on a central clock to synchronize data flow through the processor pipeline, asynchronous CPUs use handshaking logic, often referred to as "pipeline controls" or "FIFO sequencers," to coordinate operations between pipeline stages.

• Operation Without a Central Clock: In an asynchronous CPU, each stage of the pipeline proceeds to the next stage only when the current stage has completed its operation. The pipeline controller "clocks" the next stage based on the completion signal from the preceding stage. This data-driven approach eliminates the need for a global clock signal.

Advantages of Asynchronous CPUs: Unleashing Potential

• Variable Component Speeds: Components within an asynchronous CPU can run at their own optimal speeds. Unlike synchronous CPUs where all major components must be synchronized to a central clock, asynchronous components are not constrained by the slowest element in the system.

• Faster Than Worst-Case Performance: Asynchronous CPUs are not limited by the worst-case performance of the slowest stage or instruction. If an operation completes faster than anticipated (due to data characteristics, voltage/speed settings, or temperature), the next stage can immediately begin processing the results, without waiting for a clock cycle. This can lead to significant performance gains, especially in workloads with variable execution times. For example, multiplication by 0 or 1 can be significantly faster than general multiplication, and an asynchronous CPU can exploit this variability.

• Potential Benefits: Proponents of asynchronous CPUs believe these capabilities translate into:

  • Lower Power Dissipation for a Given Performance Level: By operating only when necessary and adapting to average-case performance, asynchronous CPUs have the potential to achieve lower power consumption for the same performance as synchronous CPUs.
  • Highest Possible Execution Speeds: In theory, asynchronous CPUs can achieve the highest possible execution speeds by eliminating clock-induced overhead and dynamically adapting to operating conditions.

Challenges and Counterarguments: Hurdles to Adoption

• Design Tool Limitations: A major challenge is that most CPU design tools are designed for synchronous circuits and enforce synchronous design practices. Designing an asynchronous CPU requires modifying or adapting these tools to handle clockless logic. The AMULET project, for instance, developed a specialized tool called LARD to manage the design complexity of their asynchronous ARM processor.

• Metastability Concerns: While asynchronous circuits can handle metastability robustly in certain areas, ensuring overall system stability and avoiding metastability-related issues across the entire CPU design requires careful design and verification.

• Testing and Debugging Complexity: As with asynchronous circuits in general, testing and debugging asynchronous CPUs can be more challenging than synchronous designs due to the lack of a global clock and the need to analyze event-driven behavior.

Despite these challenges, numerous asynchronous CPUs have been successfully built, demonstrating the feasibility and potential of this visionary approach.

Examples of Asynchronous CPUs: Proof of Concept

Throughout the history of computing, several notable asynchronous CPUs have been developed, showcasing the viability of the concept.

• ORDVAC (1951): A successor to ENIAC and the first asynchronous computer ever built.
• ILLIAC II (1962): The first completely asynchronous, speed-independent processor design, and at the time, the most powerful computer.
• DEC PDP-16 Register Transfer Modules (ca. 1973): Allowed the construction of asynchronous 16-bit processing elements with fixed, worst-case timing delays for each module.

Caltech's Asynchronous Microprocessors: Academic Exploration

Since the mid-1980s, Caltech has been a leading academic institution in asynchronous circuit research, designing four non-commercial CPUs to evaluate their performance and energy efficiency.

• Caltech Asynchronous Microprocessor (CAM) (1988): The first asynchronous, quasi-delay-insensitive (QDI) microprocessor from Caltech. A 16-bit RISC processor demonstrating adaptability to temperature and voltage changes. Demonstrations showed the CAM's "clock rate" naturally slowed down when heated and sped up when cooled with liquid nitrogen, showcasing its dynamic adaptation capabilities. When implemented in gallium arsenide (GaAs), it was claimed to achieve 100 MIPS.

• MiniMIPS (1998): An experimental, asynchronous MIPS I-based microcontroller. Predicted performance was around 280 MIPS at 3.3V, although implementation issues reduced actual performance.

• The Lutonium 8051 (2003): A quasi-delay-insensitive asynchronous microcontroller designed for energy efficiency, based on the Harvard architecture.

Commercial and Industrial Examples: Stepping into Reality

• Epson ACT11 (2004): The world's first bendable microprocessor, an 8-bit asynchronous chip. Its asynchronous nature was crucial for flexible electronics, as bending introduces unpredictable timing variations that are challenging for synchronous flexible processors.

• IBM SyNAPSE Chip (2014): An asynchronous, neuromorphic chip developed by IBM, featuring an exceptionally high transistor count and significantly lower power consumption compared to traditional systems on pattern recognition tasks.

Timeline of Asynchronous Computers and Processors: A Historical Perspective

The following timeline highlights key asynchronous computer and processor developments, showcasing the sustained interest and innovation in this field over decades:

• 1951: ORDVAC and ILLIAC I
• 1953: Johnniac
• 1955: WEIZAC
• 1958: Kiev (Soviet machine)
• 1962: ILLIAC II
• 1964: Atlas (University of Manchester)
• 1964 onwards: ICL 1900 series mainframes (1906A, 1906S)
• 1965 & 1970: Polish computers KAR-65 and K-202
• 1972 & 1981: Honeywell CPUs 6180 and Series 60 Level 68
• Late 1970s: Soviet bit-slice microprocessor modules (К587, К588, К1883)
• 1988: Caltech Asynchronous Microprocessor (CAM)
• 1993 & 2000: ARM-implementing AMULET processors
• 1998: MiniMIPS (asynchronous MIPS R3000)
• 2003?: XAP processor variations (bundled data, 1-of-4, dual-rail)
• 2003?: ARM-compatible processor (Yu, Furber, Plana) for security applications
• 2003: SAMIPS (synthesizable asynchronous MIPS R3000)
• 2005: "Network-based Asynchronous Architecture" processor (MIPS subset)
• 2006: ARM996HS processor (Handshake Solutions)
• 2007?: HT80C51 processor (Handshake Solutions)
• 2007: Vortex (Intel/Fulcrum Microsystem superscalar CPU)
• 2008: SEAforth multi-core processor (Charles H. Moore)
• 2010: GA144 multi-core processor (Charles H. Moore)
• Tiempo TAM16: 16-bit asynchronous microcontroller IP core
• ASPIDA: Asynchronous open-source DLX core

Why Were Asynchronous Circuits "Lost" (or Underutilized)?

Despite their demonstrated potential and numerous advantages, asynchronous circuits have not achieved mainstream adoption and remain largely a niche technology. Several factors contributed to this "lost" status:

• Dominance of Synchronous Design Paradigm: The established infrastructure of EDA tools, design methodologies, and engineering expertise is heavily biased towards synchronous design. The inertia of this established paradigm made it difficult for asynchronous design to gain widespread traction.

• Perceived Design and Verification Complexity: The perceived complexity of asynchronous design, verification, and testing, along with the lack of readily available tools and trained designers, acted as significant barriers for many companies and engineers.

• Area Overhead and Performance Trade-offs: While asynchronous circuits offer average-case performance benefits, the area overhead associated with handshaking logic and potential performance limitations in certain architectures (e.g., input-complete designs) presented trade-offs that were not always favorable compared to optimized synchronous designs, especially in performance-critical applications.

• Success of Synchronous Power Management Techniques: Advances in synchronous power management techniques, such as clock gating and dynamic voltage and frequency scaling (DVFS), mitigated some of the power consumption disadvantages of synchronous circuits, reducing the urgency for adopting asynchronous alternatives for power savings alone.

• Market and Economic Factors: The initial investment required to develop and adopt asynchronous design methodologies, tools, and expertise was substantial. In a market driven by time-to-market and cost pressures, the perceived risks and uncertainties associated with asynchronous design likely outweighed the potential long-term benefits for many commercial applications.

Conclusion: A Re-Emerging Innovation?

Asynchronous circuits, despite being largely overlooked in mainstream computing, represent a compelling and potentially transformative innovation. Their inherent advantages in power efficiency, adaptability, robustness, and average-case performance remain highly relevant, especially in the face of increasing challenges in synchronous design. As chip complexity continues to grow and power constraints become more stringent, the limitations of synchronous circuits, such as clock skew, power dissipation, and worst-case performance limitations, are becoming increasingly pronounced.

With renewed interest in energy-efficient computing, neuromorphic architectures, and specialized hardware accelerators, asynchronous design principles may be poised for a resurgence. The ongoing research and development in asynchronous methodologies, EDA tools, and design techniques could pave the way for a wider adoption of asynchronous circuits in specific application domains where their unique strengths can be fully leveraged. Asynchronous circuits, once considered a "lost" innovation, may yet have their time to shine in the future of computing.